<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
<meta name="generator" content="litedown 0.7">
<title></title>
<style type="text/css">
body {
  font-family: sans-serif;
  max-width: 800px;
  margin: auto;
  padding: 1em;
  line-height: 1.5;
  print-color-adjust: exact;
  -webkit-print-color-adjust: exact;
}
body, .abstract, code, .footnotes, footer, #refs, .caption { font-size: .9em; }
li li { font-size: .95em; }
ul:has(li > input[type="checkbox"]) { list-style: none; padding-left: 1em; }
*, :before, :after { box-sizing: border-box; }
a { color: steelblue; }
pre, img { max-width: 100%; }
pre { white-space: pre-wrap; word-break: break-word; }
pre code { display: block; padding: 1em; overflow-x: auto; }
code { font-family: 'DejaVu Sans Mono', 'Droid Sans Mono', 'Lucida Console', Consolas, Monaco, monospace; }
:not(pre, th) > code, code[class], div > .caption { background: #f8f8f8; }
pre > code:is(:not([class]), .language-plain, .language-none, .plain), .box, .figure, .table { background: inherit; border: 1px solid #eee; }
pre > code {
  &.message { border-color: #9eeaf9; }
  &.warning { background: #fff3cd; border-color: #fff3cd; }
  &.error { background: #f8d7da; border-color: #f8d7da; }
}
.fenced-chunk { border-left: 1px solid #666; }
.code-fence {
  opacity: .4;
  border: 1px dashed #666;
  border-left: 2px solid;
  &:hover { opacity: inherit; }
}
.box, .figure, .table, table { margin: 1em auto; }
div > .caption { padding: 1px 1em; }
.figure { p:has(img, svg), pre:has(svg) { text-align: center; } }
.flex-col { display: flex; justify-content: space-between; }
table {
  &:only-child:not(.table > *) { margin: auto; }
  th, td { padding: 5px; font-variant-numeric: tabular-nums; }
  thead, tfoot, tr:nth-child(even) { background: whitesmoke; }
  thead th { border-bottom: 1px solid #ddd; }
  &:not(.datatable-table) {
    border-top: 1px solid #666;
    border-bottom: 1px solid #666;
  }
}
blockquote {
  color: #666;
  margin: 0;
  padding: 1px 1em;
  border-left: .5em solid #eee;
}
hr, .footnotes::before { border: 1px dashed #ddd; }
.frontmatter { text-align: center; }
#TOC {
  a { text-decoration: none; }
  ul { list-style: none; padding-left: 1em; }
  & > ul { padding: 0; }
  ul ul { border-left: 1px solid lightsteelblue; }
}
.body h2 { border-bottom: 1px solid #666; }
.body .appendix, .appendix ~ h2 { border-bottom-style: dashed; }
.main-number::after { content: "."; }
span[class^="ref-number-"] { font-weight: bold; }
.ref-number-fig::after, .ref-number-tab::after { content: ":"; }
.cross-ref-chp::before { content: "Chapter "; }
.cross-ref-sec::before { content: "Section "; }
.cross-ref-fig::before, .ref-number-fig::before { content: "Figure "; }
.cross-ref-tab::before, .ref-number-tab::before { content: "Table "; }
.cross-ref-eqn::before, .MathJax_ref:has(mjx-mtext > mjx-c + mjx-c)::before { content: "Equation "; }
.abstract, #refs {
  &::before { display: block; margin: 1em auto; font-weight: bold; }
}
.abstract::before { content: "Abstract"; text-align: center; }
#refs::before { content: "Bibliography"; font-size: 1.5em; }
.ref-paren-open::before { content: "("; }
.ref-paren-close::after { content: ")"; }
.ref-semicolon::after { content: "; "; }
.ref-and::after { content: " and "; }
.ref-et-al::after { content: " et al."; font-style: italic; }
.footnote-ref a {
  &::before { content: "["; }
  &::after { content: "]"; }
}
section.footnotes {
  margin-top: 2em;
  &::before { content: ""; display: block; max-width: 20em; }
}
.fade {
  background: repeating-linear-gradient(135deg, white, white 30px, #ddd 32px, #ddd 32px);
  opacity: 0.6;
}

@media print {
  body { max-width: 100%; }
  tr, img { break-inside: avoid; }
}
@media only screen and (min-width: 992px) {
  body:not(.pagesjs) pre:has(.line-numbers):not(:hover) { white-space: pre; }
}
</style>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@xiee/utils@1.14.14/css/prism-xcode.min.css">
<script src="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/components/prism-core.min.js" defer></script>
<script src="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/plugins/autoloader/prism-autoloader.min.js" defer></script>
</head>
<body>
<div class="frontmatter">
</div>
<div class="body">
<pre><code class="language-r"># Depth-First Search (DFS) Algorithm
# 
# DFS is a graph traversal algorithm that explores as far as possible along each branch
# before backtracking. It uses a stack data structure (implemented via recursion here).
#
# Time Complexity: O(V + E) where V is vertices and E is edges
# Space Complexity: O(V) for the visited array and recursion stack
#
# Input: An adjacency list representation of a graph and a starting vertex
# Output: The order in which vertices are visited during DFS traversal

# Recursive DFS function
dfs_recursive &lt;- function(graph, vertex, visited, result) {
  # Mark current vertex as visited
  visited[vertex] &lt;- TRUE
  result &lt;- c(result, vertex)
  
  # Visit all unvisited adjacent vertices
  if (vertex %in% names(graph)) {
    for (neighbor in graph[[as.character(vertex)]]) {
      if (!visited[neighbor]) {
        result &lt;- dfs_recursive(graph, neighbor, visited, result)
      }
    }
  }
  
  return(result)
}

# Main DFS function
depth_first_search &lt;- function(graph, start_vertex) {
  # Get all vertices in the graph
  all_vertices &lt;- unique(c(names(graph), unlist(graph)))
  
  # Initialize visited array
  visited &lt;- rep(FALSE, max(all_vertices))
  names(visited) &lt;- 1:max(all_vertices)
  
  # Perform DFS starting from the given vertex
  result &lt;- dfs_recursive(graph, start_vertex, visited, c())
  
  return(result)
}

# Iterative DFS function using explicit stack
dfs_iterative &lt;- function(graph, start_vertex) {
  # Get all vertices in the graph
  all_vertices &lt;- unique(c(names(graph), unlist(graph)))
  
  # Initialize visited array and stack
  visited &lt;- rep(FALSE, max(all_vertices))
  names(visited) &lt;- 1:max(all_vertices)
  stack &lt;- c(start_vertex)
  result &lt;- c()
  
  while (length(stack) &gt; 0) {
    # Pop vertex from stack
    vertex &lt;- stack[length(stack)]
    stack &lt;- stack[-length(stack)]
    
    if (!visited[vertex]) {
      # Mark as visited and add to result
      visited[vertex] &lt;- TRUE
      result &lt;- c(result, vertex)
      
      # Add all unvisited neighbors to stack (in reverse order to maintain left-to-right traversal)
      if (as.character(vertex) %in% names(graph)) {
        neighbors &lt;- graph[[as.character(vertex)]]
        for (neighbor in rev(neighbors)) {
          if (!visited[neighbor]) {
            stack &lt;- c(stack, neighbor)
          }
        }
      }
    }
  }
  
  return(result)
}

# Example usage and testing
cat(&quot;=== Depth-First Search (DFS) Algorithm ===\n&quot;)
</code></pre>
<pre><code>## === Depth-First Search (DFS) Algorithm ===
</code></pre>
<pre><code class="language-r"># Create a sample graph as adjacency list
# Graph structure:
#     1
#    / \
#   2   3
#  / \   \
# 4   5   6
graph &lt;- list(
  &quot;1&quot; = c(2, 3),
  &quot;2&quot; = c(4, 5),
  &quot;3&quot; = c(6),
  &quot;4&quot; = c(),
  &quot;5&quot; = c(),
  &quot;6&quot; = c()
)

cat(&quot;Graph structure (adjacency list):\n&quot;)
</code></pre>
<pre><code>## Graph structure (adjacency list):
</code></pre>
<pre><code class="language-r">for (vertex in names(graph)) {
  cat(&quot;Vertex&quot;, vertex, &quot;-&gt; [&quot;, paste(graph[[vertex]], collapse = &quot;, &quot;), &quot;]\n&quot;)
}
</code></pre>
<pre><code>## Vertex 1 -&gt; [ 2, 3 ]
## Vertex 2 -&gt; [ 4, 5 ]
## Vertex 3 -&gt; [ 6 ]
## Vertex 4 -&gt; [  ]
## Vertex 5 -&gt; [  ]
## Vertex 6 -&gt; [  ]
</code></pre>
<pre><code class="language-r"># Test recursive DFS
cat(&quot;\nRecursive DFS starting from vertex 1:\n&quot;)
</code></pre>
<pre><code>## 
## Recursive DFS starting from vertex 1:
</code></pre>
<pre><code class="language-r">result_recursive &lt;- depth_first_search(graph, 1)
cat(&quot;Traversal order:&quot;, paste(result_recursive, collapse = &quot; -&gt; &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Traversal order: 1 -&gt; 2 -&gt; 4 -&gt; 5 -&gt; 3 -&gt; 6
</code></pre>
<pre><code class="language-r"># Test iterative DFS
cat(&quot;\nIterative DFS starting from vertex 1:\n&quot;)
</code></pre>
<pre><code>## 
## Iterative DFS starting from vertex 1:
</code></pre>
<pre><code class="language-r">result_iterative &lt;- dfs_iterative(graph, 1)
cat(&quot;Traversal order:&quot;, paste(result_iterative, collapse = &quot; -&gt; &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Traversal order: 1 -&gt; 2 -&gt; 4 -&gt; 5 -&gt; 3 -&gt; 6
</code></pre>
<pre><code class="language-r"># Test with different starting vertex
cat(&quot;\nRecursive DFS starting from vertex 2:\n&quot;)
</code></pre>
<pre><code>## 
## Recursive DFS starting from vertex 2:
</code></pre>
<pre><code class="language-r">result_from_2 &lt;- depth_first_search(graph, 2)
cat(&quot;Traversal order:&quot;, paste(result_from_2, collapse = &quot; -&gt; &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Traversal order: 2 -&gt; 4 -&gt; 5
</code></pre>
<pre><code class="language-r"># Example with a more complex graph (with cycles)
cat(&quot;\n=== Example with Cyclic Graph ===\n&quot;)
</code></pre>
<pre><code>## 
## === Example with Cyclic Graph ===
</code></pre>
<pre><code class="language-r">cyclic_graph &lt;- list(
  &quot;1&quot; = c(2, 3),
  &quot;2&quot; = c(1, 4),
  &quot;3&quot; = c(1, 5),
  &quot;4&quot; = c(2, 6),
  &quot;5&quot; = c(3, 6),
  &quot;6&quot; = c(4, 5)
)

cat(&quot;Cyclic graph structure:\n&quot;)
</code></pre>
<pre><code>## Cyclic graph structure:
</code></pre>
<pre><code class="language-r">for (vertex in names(cyclic_graph)) {
  cat(&quot;Vertex&quot;, vertex, &quot;-&gt; [&quot;, paste(cyclic_graph[[vertex]], collapse = &quot;, &quot;), &quot;]\n&quot;)
}
</code></pre>
<pre><code>## Vertex 1 -&gt; [ 2, 3 ]
## Vertex 2 -&gt; [ 1, 4 ]
## Vertex 3 -&gt; [ 1, 5 ]
## Vertex 4 -&gt; [ 2, 6 ]
## Vertex 5 -&gt; [ 3, 6 ]
## Vertex 6 -&gt; [ 4, 5 ]
</code></pre>
<pre><code class="language-r">cat(&quot;\nDFS on cyclic graph starting from vertex 1:\n&quot;)
</code></pre>
<pre><code>## 
## DFS on cyclic graph starting from vertex 1:
</code></pre>
<pre><code class="language-r">cyclic_result &lt;- depth_first_search(cyclic_graph, 1)
cat(&quot;Traversal order:&quot;, paste(cyclic_result, collapse = &quot; -&gt; &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Traversal order: 1 -&gt; 2 -&gt; 4 -&gt; 6 -&gt; 5 -&gt; 3 -&gt; 3 -&gt; 5 -&gt; 6 -&gt; 4 -&gt; 2
</code></pre>
</div>
</body>
</html>
